All the digital communication systems, such as communication, radar, remote control and test, storage system and inner operation of digital computer, and data transmission between computers, can be concluded as the model shown in FIG. 1.
The source encoder in FIG. 1 is used for promoting transmission validity. The channel encoder is employed for resisting various noise and interference during the transmission, allowing the system to have the ability of correcting errors automatically by adding redundancy information artificially, thereby ensuring the reliability of data transmission. With development of wireless digital communication and emergence of various services with high speed and strong burst, there are increasingly higher demands for the error-correcting coding techniques.
At the beginning, researches on the error-correcting code was mainly focused on linear block code based on algebra theory, later, a series of good codes such as Hamming code, cyclic code, BCH code and RS code came forth. The convolution code appearing in 1950s introduced the register during coding, increasing the relativity between the code cells, and thus obtaining higher coding gain than the block code under same complexity conditions. With the appearance of various convolution code decoding algorithms (Viterbi algorithm), the convolution code has been researched deeply and applied widely. In 1993, Frenchmen C. Berrou et al invented Turbo code, which pushed forward a large step toward the extreme of the coding performance. Enlightened by the Turbo code which is a great success, another kind of coding with similar characters and performance draws people's attention, i.e. the Low Density Parity Check Codes (LDPC codes). LDPC code is a type of liner block code that can be defined by sparse parity check matrix or bi-partite graph. It was initially discovered by Gallager, and that's why it is called Gallager code. Being silent for several decades, with the development of computer hardware and associated theories, Mackay and Neal rediscovered it and proved that it has performance approaching Shannon limit. The latest researches show that the LDPC code has the following advantages: low decoding complexity, being able of linear time coding, having performance approaching Shannon limit, being capable of parallel decoding, and superior to Turbo code in the scenario of large code size.
LDPC code is a type of linear block code based on sparse check matrix. The encoding and decoding of low complexity are realized rightly by utilizing the sparsity of the check matrix of the LDPC code, thereby making the LDPC code practicable. The Gallager code mentioned above is a type of regular LDPC code (regular ldpcc), while Luby and Mitzenmacher etc. spreaded the Gallager code and advanced the irregular LDPC code (irregular ldpcc). The code that Gallager invented originally has regular code structure; its check matrix is sparse matrix with each row having the same number of 1s, and each column also having the same number of 1s. M. G. Luby believes that if the number of non-zero elements in the rows or columns of the check matrix is allowed to vary, and at the same time the sparsity of the matrix is ensured, then the decoding algorithm of the coding is still applicable, while the performance of the coding can be improved greatly so that it can reach, or even exceed the performance of the Turbo code. The reasons are in this type of coding structure, if the left node and the right node corresponding to the bipartite graph have appropriate degree distribution, there would be a waveform effect when decoding, which will promote the performance of decoding greatly. The irregular code is rightly this type of low density coding that permits different degrees for the same kind of nodes, while the code that Gallager advanced originally is called regular code correspondingly.
For the LDPC codes of medium and short sizes, short cycles in the bi-partite graph will decrease the code performance greatly, which makes the research on how to construct non-short-cycles become ever important. Currently, the relevant construction methods mainly include combination construction, limited geometrical construction, group theory construction and graph theory construction etc, which, however, are mainly oriented to the regular codes, and have many limitations with too strong theorization and low practicability, J. Campello etc. put forward the extended Bit-Filling algorithm, by which, LDPC codes with high code rate and definite girth (“girth” means the length of the shortest cycle of the bi-partite graph of LDPC codes) or LDPC codes with definite code rate and large girth can be designed. It is a general method, with proper amendments, it can be used to design the irregular LDPC codes with ensured girth. Therefore, how to find the LDPC codes having as few of short cycles as possible becomes very important.
Currently, the method of constructing the LDPC codes with freely changeable code sizes through identity matrix and cyclic shift matrices thereof is raised in many documents. Such LDPC code with block cyclic parity check matrices becomes a hot research subject presently. However, the code construction method for such LDPC code having as few of the short cycles as possible is now not very comprehensive yet.
The LDPC code based on the identity matrix and the cyclic shift matrices thereof becomes a key research subject in the academe currently, since it has freely changeable code sizes, its coding is simply to realize, and the degree distribution and girth distribution can remain unchanged during the extension. The LDPC code based on the identity matrix and the cyclic shift matrices thereof constructed currently does not take the effect of the girth and the relationship between the code size and the girth into full consideration, causing that the bit error rate (BER) curve decreases under a relatively high signal noise rate (SNR) at a dramatically slowed down speed, the error floor often appears, and thereby degrading the performance. It becomes a problem demanding prompt solution that how to eliminate the error floor of the LDPC code, accelerate the decreasing speed of the BER curve, and improve the performance of the LDPC code under the case of high SNR.